package com.logbug.algorithm;

/**
 * @author chenlin
 */
public class FindOddNumber {
    public static void main(String[] args) {
        int[] arr = new int[]{11, 13, 11, 13, 14};
        findOne(arr);
        int[] arr2 = new int[]{11, 13, 11, 13, 14, 15};
        findTwo(arr2);
    }

    /**
     * 找出数组中唯一出现奇数次的数
     * @param arr
     */
    private static void findOne(int[] arr) {
        int theOne = 0;
        for (int i = 0; i < arr.length; i++) {
            theOne ^= arr[i];
        }
        System.out.println("theOne: " + theOne);
    }

    /**
     * 找出数组中两个出现奇数次的数
     * @param arr
     */
    private static void findTwo(int[] arr) {
        int eor = 0, theOne = 0;
        for (int i = 0; i < arr.length; i++) {
            eor ^= arr[i];
        }
        // 取出亦或值的右边第一位不为0的位作为分类器
        // 目的就是将theOne与otherOne分开，偶数次的数不影响结果
        int separator = eor & (~eor + 1);
        for (int i = 0; i < arr.length; i++) {
            if ((arr[i] & separator) == 1) {
                theOne ^= arr[i];
            }
        }
        int otherOne = eor ^ theOne;
        System.out.printf("theOne: %s , otherOne: %s", theOne, otherOne);
    }
}
